СОДЕРЖАНИЕ
4.1.Списки
4.2.Операции над списками
4.3. Стандартные предикаты
![]()
Списки - это упорядоченный набор объекта или элементов списка, заключённых в квадратные скобки и отделённых друг от друга. Список может содержать произвольное количество элементов, ограничениями является доступность операционной памяти. Список не содержащий элементов называется пустым и обозначается в квадратных скобках, внутри которых ничего нет. Обработка списков базируется на понятии разбиения списка - на голову и хвост. Голова - первый элемент списка, хвост - остальная часть. Для использования списка в Прологе необходимо
необхадимо записать следующее:
<имя домена> = <тип эл-та>*
Пример объявления списка:
DOMAINS
g1=integer*
g2=symbol*
PREDICATES
f[g1]
l[g2]
Примеры списков:
[10,5,7,12]
[1.1,5.8,11.5]
["январь","февраль","декабрь"]
Операция разбиения списка на голову и хвост:
![]() |
Пример 1. Программа отображения элементов списка:
DOMAINS
List1 = integer*
List2 = symbol*
PREDICATES
name [List1]
score [List2]
CLАUSES
name ["Иванов","Сидоров","Петров"].
score [1,2,3,4].
GOAL
Name [X],
Name [ _, Y, _ ],
Score [Z, _ , F, _ ], write(X,” ”,Y,” ”,Z,” ”,F)
При использование в
Пролог – программе списков с произвольным
числом элементов используется метод разделения
списка на голову и хвост. Этот метод обеспечивает
рекурсивную обработку списка. Операция
разделения списка обозначается вертикальной
чертой и записывается в следующем виде: [Head | Tail].
Пример 2. Программа распечатки содержимого списка:
DOMAINS
List1=integer*
List2=symbol*
PREDICATES
Print _ list (List1)
Print _ list (List2)
CLAUSES
Print _ list ([ ]).
Print _ list ([Head | Tail] ):-write (Head), nl,
Print _ list (Tail).
GOAL
Print
_ list ( [1,2,3,4] )
В данной программе данные могут быть представлены в виде символьного или целого типа. В программе реализуется рекурсивный метод обработки списков. Первое предложение программы print_list([ ]) означает, что пустой список является условием выхода программы из рекурсии, используемом во втором предложении. Сначала запрос print_list([1,2,3,4]) сопоставляется с первым предложением print_list([ ]). Это сопоставление заканчивается неуспехом, т.к. [1,2,3,4]?[ ]. Далее этот запрос сравнивается со вторым предложением. Операция завершается успешно. В левой части списка происходит разделение списка на голову и хвост, а в правой части - вывод на экран головы списка. Затем выполняется предикат nl- переход на следующую строку. Далее формируется рекурсивный вызов print_list([2,3,4]), который обращается к процедуре print_list([ ]) и т.д.
Пример 3. Программа подсчета суммы
произведения двух списков X, Y.
DOMAINS
Vector=integer*
PREDICATES
prod(Vector,Vector,Vector)
CLAUSES
prod([ ],[ ],0).
prod([X|Xs],[Y|Ys],S):-prod(Xs,Ys,Sp), S=X*Y+Sp.
GOAL
prod([1,2,3],[7,8,9],Res), write(“Res=”,Res)
Действия Пролог-программы
можно представить в виде таблицы:
Вызов предиката |
Подстановка |
Хвостовые вычисления |
Результаты вычислений |
prod([1,2,3],[7,8,9],Res) |
X=1, У=7, Xs=[2,3], S=[8,9] Res=S |
S=X?Y+Sp |
S=1?7+43=50 prod(Xs,Ys,Sp) |
prod([2,3],[8,9],S) |
X=2, Y=8 Xs=[3], Ys=[9] Res=S |
Sp=X?Y+Sp |
S=16+27=43 |
prod([3],[9],S) |
X=3, Y=9 Xs=[ ], Ys=[ ] Res=S |
S=X?Y+Sp |
S=3?9=27 |
prod([ ],[ ],0) |
Выход
из рекурсии
|
||
Пример 4. Получить индекс заданного элемента
в списке.
DOMAINS
L=integer*
X=integer
PREDICATES
poluch(L,X,X)
CLAUSES
poluch([X|Y],1,X).
poluch([W|Y],N,X):-M=N-1,poluch(Y,M,X).
GOAL
poluch([1,2,3,4],3,X),write(X)
Рассмотрим
механизм пошаговой работы программы:
CALL: goal() /* внешний
запрос */
CALL: poluch([1,2,3,4],3,_) /* вызов
процедуры получения индекса для
элемента
3 */
REDO: poluch([1,2,3,4],3,_) /* процедура
сначала сопоставляется с первым предложением
правила,
которое завершается неуспешно, затем со вторым
предложением, операция
разделения списка на голову и хвост, отделяется первый
элемент списка и заносится в стек, переменная M % получает
значение 3-1=2: */
2=2
CALL: poluch([2,3,4],2,_) /* выполняется вторая
часть предложения,
вызов рекурсивной
процедуры poluch(Y,M,X) */
REDO: poluch([2,3,4],2,_) /* процедура
сопоставляется с первым предложением, т.к.
сопоставление заканчивается неуспешно, то
происходит откат, затем выполняется второе
предложение, отделяется второй элемент списка и
заносится в стек, переменная получает значение M=2-1=1: */
1=1
CALL: poluch([3,4],1,_) /* выполняется
вторая часть предложения,
вызов рекурсивной
процедуры poluch(Y,M,X), процедура
сопоставляется с первым предложением, при этом
сопоставление заканчивается успешно: */
RETURN: poluch([3,4],1,3)
/* C этого
момента вычисления для переменной М заканчиваются,
начинаются стековые операции, т. е.
последовательный вывод значений из стека: */
RETURN:
poluch([2,3,4],2,3)
RETURN:
poluch([1,2,3,4],3,3)
write(3)
![]()
1. Операция: принадлежность
к списку.
Составление
программы для принадлежности может быть
основано на следующих соображениях:
1) Х есть голова L, либо
2) Х принадлежит
хвосту L.
Это можно записать в виде двух предложений, первое из которых есть простой факт, а второе-правило:
принадлежит(Х, [X|Хвост]).
принадле жит(Х, [Голова|Хвост]):-принадлежит(Х, Хвост).
Примеры:
принадлежит(b, [a,b,c])
принадлежит([b,c], [a,[b,c]])
2. Операция: сцепление
(конкатенация).
Программа на определение отношения
конкатенация:
конк([],L,L).
конк([X|L1],L2,[X|L3]):-конк(L1,L2,L3).
Применение: составленную программу
можно теперь использовать для
а)
сцепления заданных списков, например:
?-конк([a,b,c],[1,2,3],L).
L=[a,b,c,1,2,3]
б) для разбиения заданного
списка на две части:
?-конк(L1,L2,
[a,b,c]).
L1=[ ]
L2=[a,b,c];
L1=[a ]
L2=[b,c];
L1=[a,b]
L2=[c];
L1=[a,b,c]
L2=[];
в) для поиска в
списке комбинации элементов, отвечающей
некоторому условию, задаваемому в виде шаблона
или образца:
?-конк(Do, [may|_]),[jan,feb,mart,apr,may,iun, iul, avg,
sent, okt, nov, dec].
Do=[jan,feb,mart,apr]
3. Операция: добавление
элемента в список.
Программа
добавления элемента в список:
добавить(X,
L,
[X|L]).
4. Операция: удаление
элемента из списка.
Программа
удаления элемента из списка:
удалить(Х, [X|Хвост], Хвост).
удалить(Х, [У|Хвост],
[У|Хвост1]):-удалить(Х, Хвост,
Хвост1).
Пример:
?-удалить(a,[a,b,a,a],L).
L=[b,a,a];
L=[a,b,a];
L=[a,b,a].
Применение:
?- удалить(a,L,[1,2,3]).
L=[a,1,2,3];
L=[1,a,2,3];
L=[1,2,a,3];
L=[1,2,3,a];
5. Операция: подсписок.
Программа
подсписка:
подсписок(S, L):-конк(L1, L2, L), конк(S, L3, L2).
Его
можно сформулировать так:
S является
подсписком L, если
1) L можно
разбить на два списка L1, L2 и
2) L2 можно
разбить на два списка S и L3.
?-подсписок(S, [a,b,c])
S= [ ];
S=[a];
S=[a,b];
S=[a,b,c];
S=[b];
6. Операция:
перестановки.
Программа для отношения перестановка основывается на рассмотрении двух случаев в зависимости от вида первого списка:
1) Если первый список пуст, то и второй список должен быть пустым.
2) Если первый список не пуст, тогда он имеет вид [Х|L], и перестановку такого списка можно построить следующим образом: вначале получить список L1 – перестановку L, а затем внести Х в произвольную позицию L1. Программа на языке Пролог:
перестановка([ ], [ ]).
перестановка([X|L], P):- перестановка(L, L1), внести(X, L1, P).
![]()
Стандартные (встроенные в
систему) предикаты выполняют разнообразные
функции по выполнению ввода-вывода переменных
различных типов, работе с файлами, выполнению
функций DOS, обработке строк,
поддержке графического режима, обеспечение
интерфейса с другими системами программирования
(C, Паскаль) и т. д. Всего в
системе содержится более 200 стандартных
предикатов.
Для использования стандартных
предикатов необходимо знать имя предиката,
способы его вызова, число и типы значений
параметров, а также режимы их передачи. Режим
передачи описывается обычно в виде шаблона,
который показывает, какие из параметров является
входными (в шаблоне обозначается i или вх), а какие выходными (в
шаблоне обозначается o или вых) для предиката.
Приведем остальные стандартные предикаты
Турбо-Пролога в следующем формате:
предикат(список
аргументов) (типы доменов):(шаблон).
makewindow (НомОкна, АтрЭкр,
АтрРамки, СтрРамки, Строка, Столбец,
Высота, Ширина, ЧиститьОкно,
ПозСтрРамки, ЗнакиГраницы) (integer, integer, integer, string, integer, integer, integer, integer, integer, integer, string): (вх, вх, вх, вх, вх, вх, вх, вх,
вх, вх, вх), (вых, вых, вых, вых, вых, вых, вых, вых,
вых, вых, вых). Предикат makewindow создает окно с номером
аргумент НомОкна. Остальные аргументы предиката
имеют следующий смысл:
АтрЭкр
– определяет цвет символа и фона;
АтрРамки
– при отличном от нуля значений рисуется
граница-линия обрамление окна;
СтрРамки
– указывает строку, помещаемую в центре верхней
границе контура окна;
Строка,
Столбец – вертикальная и
горизонтальная координаты верхнего левого угла
окна;
Высота,
Ширина – высота (число строк) и ширина
(число колонок) окна;
ЧиститьОкно
определяет, будет ли чиститься окно после его
создания; 0 = Не чистить окно; 1 = Чистить окно;
ПозСтрРамки
определяет место размещения заголовка окна
(внутри верхней линии рамки окна):-1=Заголовок в
центре; N=Размещает заголовок с
указанной позиции;
ЗнакиГраницы
описывают как рисовать рамку окна.
Этот аргумент состоит строго
из шести символов, обозначающих: верхний левый
угол, верхний правый угол, нижний левый угол,
нижний правый угол, горизонтальную линию и
вертикальную линию соответственно. Например:
“\218\191\192\217\196\179” – границы из одной линий;
“\201\187\200\188\205\186” – граница из двух линий; “++++|-”
– другой вариант описания границы.
Readchar(СимволПеременной)(char):(вых) - читает единственный
символ с текущего устройства ввода, которым
является по умолчанию клавиатура, пока оно будет
изменено с помощью Readdevice.
Readdevice(СимволИмяФайла)(symbol):(вх), (вых) - устанавливает или
выдает текущее устройство вывода, (вх): назначает
текущее устройство ввода на открытый файл с
данным СимволичИмяФайла. Открываемый файл может
быть один из стандартных файлов или любым файлом
пользователя с символическим именем, открытым
для чтения или модификации. (вых): связывает
СимвИмяФайла с именем текущего устройства ввода.
Стандартные файлы, которые могут быть открыты
для ввода: com1 – чтение из
последовательного порта связи; keyboard – чтение с клавиатуры (по
умолчанию); stdin – чтение из стандартного
ввода DOS.
Readint(ПеременнаяЦел)(integer):(вых) - читает целое число с
текущего устройство ввода. Преобразование
символов не осуществляется, пока Readint не встретит символ
возврата каретки (ASCII 13).
Readln (переменная строка) (string):(вых) - считывает строку символов с текущего устройства ввода до символ возврата каретки (ASCII 13) Самая большая строка которая может быть прочитана на экране, содержит 147 символов.
Readreal (перменная вещ)(real):(вых). Читает вещественное число с текущего устройства ввода, пока не прочитается символ возврата каретки. Если нажать ESC (ключ), Readreal немедленно не согласуется. Readreal так же не согласуется, если символ не образует правильное вещественное число или они определяют вещественное число, превышающее допустимые границы.
Write (е1,е2,е3….еN):(вх,вх,вх….вх) - вводит значение констант или переменных в текущее окно или на текущее устройство ввода. Write может быть связан с произвольным не нулевым числом аргументов ei. Аргументы не могут быть свободными переменными.
Writedevice (симвИмяФайла)(symbol)(вх),(вых) - устанавливает или выдает текущее устройство ввода. (вх): переназначает текущее устройство ввода в открытый файл с данным СимвИмяФайла. Открытый файл может быть одним из стандартных символических файлов или любым пользовательским файлом, открытым для записи или для модификации. (вых): связывает символьное имя файла с текущим устройством ввода. Для вывода могут использоваться следующие встроенные файлы: COM1 – последовательный порт; printer – параллельный порт принтера; screen – экран монитора; stdout – стандартный вывод DOS: stderr – файл стандартных ошибок.
Removewindow/0 - удаляет текущее окно и переходит в предшествующему окну.
Writef (ФорматСтр, Арг1, Арг2, Арг3….)(вх, вх….вх) - выполняет форматированный вывод. Аргументы Арг1 – АргN могут быть константами или переменными. Форматы задаются в виде строки ФорматСтр обычного текста, где символы % отмечают положение аргумента строки. Допустимые спецификации формата содержат обычные символы, которые печатаются без модификации, и формат спецификации формы % - m.pf. формат спецификации означает: - (дефис) показывает, что поле выравнивается слева; m поле – десятичное число, описывающий минимальный размер поля; p поле описывает или точнее представление числа с плавающей точкой, или максимальное количество напечатанных в строке символов. f поле описывает следующие форматы:
f - формат вещественного в фиксированной десятичной системе счисления;
Е- формат вещественного в экспоненциальной форме представления;
G- формат вещественного в коротком формате (используется по умолчанию);
D- формат символов или целых десятичных чисел;
U- формат символов или целых чисел как десятичное число без знака;
Х- формат символов или целых чисел как шестнадцатеричного числа;
С- формат символов или целых чисел как символа;
R- использует аргумент как ссылку на номер указателя базы данных;
Х- использует аргумент как длинное шестнадцатеричное число (строки, номер указателя базы данных);
S- формат как строка (символов и строк).
Asserta (<факт>)(dbasedom)(вх) - заносит факт (утверждение) в начало резидентной базы данных (домен, обозначенный как basedom, автоматически объявляется для каждого предиката из раздела database).
Assertz (X)(dbasedom):(вх) - заносит факт (утверждение) Х в конце резидентной базы данных.
Retract (X):(вх) - в базе данных осуществляется поиск утверждения, голова и тело которого сопоставляется с термом Х. Первое такое утверждение удаляется из базы данных. Аргумент (терм Х) должен быть конкретизирован составным термом:
Retractall (X):(вх) - удаляет из базы данных все утверждения, функтор и арность которых сопоставимы с Х.
Frontchar
(Стр, ПермСимв, ОстСтр,)(string, char, string):(вх, вых,
вых),(вх, вх, вых,), (вх, вых, вх),(вх, вх, вх),(вых, вх,
вх) (вх, вых, вых): присваевает первый символ
строки Стр переменной ПерСимв, а остаток строки
– переменной ОстСтр. Возможны и другие
комбинации входных и выходных аргументов.
Frontstr(ЧислСимв,Стр1,НачСтр,Стр2) (integer,string,string,string) :(вх, вх, вых, вых) - присваивает первые ЧислСимв символов строки Стр1 пересменной НачСтр, а остаток строки – переменной Стр2.
Fronttoken (Стр, Знак, ОстСтр)(string, string, string):(вх, вых, вых),(вх, вх, вых),(вх, вых, вх), (вх, вх, вх), (вых, вх, вх) (вх,вых,вых) - переменной Стр присваевается результат конкатенации знак и ОстСтр. Знак может быть группой символов задающих допустимое имя, либо символьным представлением числа, либо одиночным символом, отличным от пробела. В других комбинациях входных и выходных аргументов должны быть обозначены минимум 2 аргумента предиката:
Cursor (Стр, Кол) (integer, integer):(вх, вх), (вых, вых), (вх, вх) - помещает курсор в позицию с координатами (Стр, Кол).